# -*- coding: utf-8 -*-

import sys
import re
import math
import multiprocessing as mp

class Node:
    pass


def kdtree(point_list, depth=0):
    
    if not point_list:
        return
    
    k = len(point_list[0]) # Assume que todos os pontos tem a mesma dimensao
    axis = depth % k
 
    point_list.sort(key=lambda point: point[axis])
    
    median = len(point_list)/2 # choose median

    node = Node()
    node.location = point_list[median]
    
    node.left_child = kdtree(point_list[0:median], depth+1)
    node.right_child = kdtree(point_list[median+1:], depth+1)
    return node

def main():
    arq = open(sys.argv[1])
    p = int(sys.argv[2])
    linhas = arq.readlines()
    
    points = []
    
    for i, linha in enumerate(linhas):
        d = re.search("(?P<a>\d{1,3}) (?P<b>\d{1,3}) (?P<c>\d{1,3})", linha)
        points.append((int(d.group('a')), int(d.group('b')), int(d.group('c'))))
        if i >= p-1:
            break
    
    nos = []
    
    profundidade = math.log(NP, 2) % 3
    
    slice = (p + NP - 1) / NP
    
    for i in range(NP):
        if i == 0:
            ini = 0
        else:
            ini = i * slice
        fim = (i + 1) * slice
        if fim > p:
            fim = p
        
        
    nos.append(kdtree(points[ini:fim], int(profundidade)))
    
    #t = kdtree(points)
    #print t.location
    #print t.left_child.location
    #print t.right_child.location

if __name__ == "__main__":
    NP = 8
    main()